package org.raymond.iworks.study.basic.structure.tree.threadedbinarytree;

import java.util.HashMap;
import java.util.Map;

/**
 * @author raymond
 * @version V1.0
 * @Description: 将数列{1,3,6,8,10,14}构建成一颗二叉树
 *                1(0)
 *        3(1)              6(2)
 *    8(3)    10(4)    14(5)   [7]
 * [1] [2]  [3] [4]  [5]  [6]
 *
 * 这是一个完全二叉树,小括号是数组下标,中括号(7个)是准备存放线索的空指针域
 * 问题分析:
 * 1) 当我们对上面的二叉树进行中序遍历时,数列为(8,3,10,1,14,6}
 * 2) 但是6,8,10,14这几个节点的左右指针,并没有完全的利用上
 * 3) 如果我们希望充分的利用各个节点的左右指针,让各个节点可以指向自己的前后节点,怎么办?
 * 4) 解决方案:线索二叉树
 * 线索二叉树介绍:
 * 1) n个节点的二叉链表中含有n+1 [公式2n-(n-1)=n+1] 个空指针域.利用二叉链表中的空指针域,存放指向 该节点在某种遍历次序下
 * 的前驱和后继节点 的指针(这种附加的指针称为"线索")
 * 2) 这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree).根据线索性质的不同,
 * 线索二叉树可分为前序线索二叉树,中序线索二叉树和后序线索二叉树 三种
 * 3) 一个节点的前一个节点,称为前驱节点
 * 4) 一个节点的后一个节点,称为后继节点
 *
 * 将数列(8,3,10,1,14,6}的二叉树线索化:
 *                1(0)
 *        3(1)              6(2)
 *    8(3)    10(4)    14(5)   [7]
 * [1] [2]  [3] [4]  [5]  [6]
 *
 * 所有线索的赋值情况:
 * 8.left=8[1]=null
 * 8.right=8[2]=3
 * 10.left=10[3]=3
 * 10.right=10[4]=1
 * 14.left=14[5]=1
 * 14.right=14[6]=6
 * 6.left=14
 * 6.right=6[7]=null
 *
 * 说明: 当线索化二叉树后,Node节点的属性left和right,有如下情况
 * 1) left指向的是左子树,也可能是指向前驱节点.比如"1(0)"节点的left指向左子树“3(1)”,
 * 而"10(4)"节点的left指向的是前驱节点
 * 2) right指向的是右子树,也可能是指向后继节点.比如"1(0)"节点的right指向右子树“6(2)”,
 * 而"10(4)"节点的right指向的是后继节点
 *
 * 遍历线索化二叉树
 * 说明:对中序线索化二叉树进行遍历
 * 分析:因为线索化后,各个节点的指向有变化,因此原来的遍历方式不能使用.这时需要使用新的方式遍历线索化二叉树,
 * 各个节点可以通过线型方式遍历,因此无需使用递归方式,这样也提高了遍历的效率.遍历的次序应当和中序遍历保持一致.
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        // 测试中序线索二叉树的功能
        var root = new HeroNode(1, "tom");
        var node2 = new HeroNode(3, "jack");
        var node3 = new HeroNode(6, "smith");
        var node4 = new HeroNode(8, "mary");
        var node5 = new HeroNode(10, "king");
        var node6 = new HeroNode(14, "dim");

        // 手动创建树
        root.left=node2;
        root.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;

        // 初始化树
        var threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.root=root;

        // 线索化
        threadedBinaryTree.threadedNodes();

        // 测试:检查10节点的前驱节点和后继节点
        var leftNo = node5.left==null?-1:node5.left.no;
        var rightNo = node5.right==null?-1:node5.right.no;
        System.out.printf("%d的前驱节点是%d,后继节点是%d\n", node5.no, leftNo, rightNo);

        // 当线索化二叉树后,不能使用原来的遍历方法
        // 需要在判断是否叶节点时,增加leftType和rightType的判断
        //threadedBinaryTree.infixOrder();
        threadedBinaryTree.threadedList();
    }
}

//实现了线索化功能的二叉树
class ThreadedBinaryTree {
    public HeroNode root;
    // 为了实现线索化,需要创建 要给指向当前节点的前驱节点的指针
    // 在递归线索化时,pre总是保留指向前一个节点的引用
    public HeroNode pre;

    public void threadedNodes(){
        threadedNodes(root);
    }
    // 遍历线索化二叉树的方法
    public void threadedList(){
        // 定义一个变量,存储当前遍历的节点,从root开始
        HeroNode node = root;
        while(node != null){
            // 循环找到leftType=1的节点,第一个找到的就是最左的节点(8节点)
            // 后面随着遍历而变化,当leftType=1时,说明该节点是按照线索化处理后的有效节点
            while(node.leftType==0){
                node = node.left;
            }
            // 打印当前节点
            System.out.println(node);
            // 如果当前节点的右指针指向的是后继节点,就一直输出
            while(node.rightType==1){
                // 获取到当前节点的后继节点
                node = node.right;
                System.out.println(node);
            }
            // 替换这个遍历的节点
            node = node.right;
        }
    }
    /**
     * @param node 当前需要线索化的节点
     */
    public void threadedNodes(HeroNode node){
        if(node==null){
            System.out.println("无法线索化null节点");
            return;
        }
        // 中序遍历线索化
        // 1,先线索化左子树
        threadedNodes(node.left);
        // 2,然后线索化当前节点
        // 2.1 处理当前节点的前驱节点
        // 以8节点来理解
        // 8节点的.left=null,8节点的leftType=1
        if(node.left==null){
            // 让当前节点的左指针指向前驱节点
            node.left=pre;
            // 修改当前节点的左指针的类型为前驱节点
            node.leftType=1;
        }
        // 2.2 处理后继节点,(这是下一次递归中处理的,结合2.3理解)
        // 比如先处理8节点,8节点的前驱节点为null,则这里跳过,到2.3
        // 下一次递归会处理3节点,3节点的前驱节点在本次递归的2.3中被设置为8节点
        if(pre!=null && pre.right==null){
            // 让前驱节点的右指针指向当前节点
            pre.right=node;
            // 修改前驱节点的右指针类型
            pre.rightType=1;
        }
        // 2.3 每处理一个节点后,让当前节点作为下一个节点的前驱节点
        pre = node;
        // 3,最后线索化右子树
        threadedNodes(node.right);
    }

    // 前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }

    // 后续遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }

    // 前序查找
    public HeroNode preSearch(int no) {
        if (this.root == null) {
            System.out.println("二叉树为空,无法查找");
            return null;
        }
        return this.root.preSearch(no);
    }

    // 中序查找
    public HeroNode infixSearch(int no) {
        if (this.root == null) {
            System.out.println("二叉树为空,无法查找");
            return null;
        }
        return this.root.infixSearch(no);
    }

    // 后序查找
    public HeroNode postSearch(int no) {
        if (this.root == null) {
            System.out.println("二叉树为空,无法查找");
            return null;
        }
        return this.root.postSearch(no);
    }

    public void delNode(int no) {
        if (this.root == null) {
            System.out.println("二叉树为空,无法删除节点");
        } else {
            if (this.root.no == no) {
                this.root = null;
            } else {
                this.root.delNode(no);
            }
        }
    }

    public void cleanCountMap() {
        for (Integer no : HeroNode.countMap.keySet()) {
            HeroNode.countMap.put(no, 0);
        }
    }
}

class HeroNode {
    public int no;
    public String name;
    public HeroNode left;
    public HeroNode right;
    /**
     * 0-表示指向左子树,1-表示指向前驱节点
     */
    public int leftType;
    /**
     * 0-表示指向右子树,1-表示指向后继节点
     */
    public int rightType;
    public static Map<Integer, Integer> countMap = new HashMap<>();

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
        countMap.put(no, 0);
    }

    @Override
    public String toString() {
        Integer count = countMap.get(no);
        return String.format("HeroNode [no=%s, name=%s], 比较次数=%d", no, name, count);
    }

    // 前序遍历
    public void preOrder() {
        // 输出当前节点
        System.out.println(this);
        // 递归向左子树前序遍历
        // 线索化后,判断条件加上leftType==0
        if (this.left != null && this.leftType==0) {
            this.left.preOrder();
        }
        // 递归向右子树前序遍历
        // 线索化后,判断条件加上rightType==0
        if (this.right != null && this.rightType==0) {
            this.right.preOrder();
        }
    }

    // 中序遍历
    public void infixOrder() {
        // 递归向左子树中序遍历
        if (this.left != null && this.leftType==0) {
            this.left.infixOrder();
        }
        // 输出当前节点
        System.out.println(this);
        // 递归向右子树中序遍历
        if (this.right != null && this.rightType==0) {
            this.right.infixOrder();
        }
    }

    // 后序遍历
    public void postOrder() {
        // 递归向左子树后序遍历
        if (this.left != null && this.leftType==0) {
            this.left.postOrder();
        }
        // 递归向右子树后序遍历
        if (this.right != null && this.rightType==0) {
            this.right.postOrder();
        }
        // 输出当前节点
        System.out.println(this);
    }

    // 前序查找
    public HeroNode preSearch(int no) {
        HeroNode result = null;
        int count = countMap.get(no);
        // 判断当前节点是否符合条件
        count++;
        countMap.put(no, count);
        System.out.printf("===前序比较===: this.no=%d, input.no=%d, count=%d\n", this.no, no, count);
        if (this.no == no) {
            return this;
        }
        // 递归向左子树前序查找
        if (this.left != null) {
            result = this.left.preSearch(no);
            if (result != null) {
                return result;
            }
        }
        // 递归向右子树前序查找
        if (this.right != null) {
            result = this.right.preSearch(no);
            if (result != null) {
                return result;
            }
        }
        return null;
    }

    // 中序查找
    public HeroNode infixSearch(int no) {
        HeroNode result = null;

        // 递归向左子树中序查找
        if (this.left != null) {
            result = this.left.infixSearch(no);
            if (result != null) {
                return result;
            }
        }
        // 判断当前节点是否符合条件
        int count = countMap.get(no);
        count++;
        countMap.put(no, count);
        System.out.printf("===中序比较===: this.no=%d, input.no=%d, count=%d\n", this.no, no, count);
        if (this.no == no) {
            return this;
        }

        // 递归向右子树中序查找
        if (this.right != null) {
            result = this.right.infixSearch(no);
            if (result != null) {
                return result;
            }
        }
        return null;
    }

    // 后序查找
    public HeroNode postSearch(int no) {
        HeroNode result = null;
        // 递归向左子树前序查找
        if (this.left != null) {
            result = this.left.postSearch(no);
            if (result != null) {
                return result;
            }
        }
        // 递归向右子树前序查找
        if (this.right != null) {
            result = this.right.postSearch(no);
            if (result != null) {
                return result;
            }
        }
        // 判断当前节点是否符合条件
        int count = countMap.get(no);
        count++;
        countMap.put(no, count);
        System.out.printf("===后序比较===: this.no=%d, input.no=%d, count=%d\n", this.no, no, count);
        if (this.no == no) {
            return this;
        }
        return null;
    }

    public void delNode(int no) {
        if (this.left == null && this.right == null) {
            System.out.println("二叉树为空,不能删除节点");
            return;
        }
        if (this.left != null && this.left.no == no) {
            System.out.println("找到待删除的节点,no=" + no);
            // 左子节点下面同时存在左左子节点和左右子节点,需要用左左子节点替代左子节点
            // 如果左左子节点存在左左右子节点,则将左右子节点追加到左左右最右边节点下
            //   2<-1->3
            //7<-2->6
            if (this.left.left != null && this.left.right != null) {
                HeroNode tempLeft = this.left.left;
                HeroNode tempRight = this.left.right;
                this.left = tempLeft;
                appendNodeToRight(this.left, tempRight);
            } else if (this.left.left != null) {
                this.left = this.left.left;
            } else if (this.left.right != null) {
                this.left = this.left.right;
            }
            return;
        }
        // 2<-1->3
        //    5<-3->4
        if (this.right != null && this.right.no == no) {
            System.out.println("找到待删除的节点,no=" + no);
            if (this.right.left != null && this.right.right != null) {
                HeroNode tempLeft = this.right.left;
                HeroNode tempRight = this.right.right;
                //System.out.printf("tl:%s, tr:%s, r:%s\n", tempLeft,tempRight,this.right);
                this.right = tempLeft;
                appendNodeToRight(this.right, tempRight);
            } else if (this.right.left != null) {
                this.right = this.right.left;
            } else if (this.right.right != null) {
                this.right = this.right.right;
            }
            return;
        }
        if (this.left != null) {
            this.left.delNode(no);
        }
        if (this.right != null) {
            this.right.delNode(no);
        }
    }

    public void appendNodeToRight(HeroNode node, HeroNode appendedNode) {
        if (node.right != null) {
            appendNodeToRight(node.right, appendedNode);
        } else {
            node.right = appendedNode;
        }
    }
}
